package com.lili.backtrack;

/**
 * @Auther: 李 力
 * @Date: 2024/8/21
 * @Description: 解数独
 * @version: 1.0
 */
public class LeetCode37 {
    public static void solveSudoku(char[][] board) {
        /*
         * 行冲突状态
         **/
        boolean[][] ca = new boolean[9][9];

        /*
         * 列冲突状态
         * */
        boolean[][] cb = new boolean[9][9];

        /*
         * 九宫格冲突状态
         * */
        boolean[][] cc = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char ch = board[i][j];
                if (ch != '.') {
                    ca[i][ch - '1'] = true;
                    cb[j][ch - '1'] = true;
                    cc[i / 3 * 3 + j / 3][ch - '1'] = true;
                }
            }
        }
        dfs(0, 0, board, ca, cb, cc);
    }

    private static boolean dfs(int i, int j, char[][] board, boolean[][] ca, boolean[][] cb, boolean[][] cc) {
        while (board[i][j] != '.') {
            if (++j >= 9) {
                j = 0;
                i++;
            }
            if (i >= 9) {
                return true;
            }
        }
        for (int x = 1; x <= 9; x++) {
            if (ca[i][x - 1] || cb[j][x - 1] || cc[i / 3 * 3 + j / 3][x - 1]) {
                continue;
            }
            board[i][j] = (char) (x + '0');
            ca[i][x - 1] = true;
            cb[j][x - 1] = true;
            cc[i / 3 * 3 + j / 3][x - 1] = true;
            boolean r = dfs(i, j, board, ca, cb, cc);
            if (r) {
                return r;
            }
            board[i][j] = '.';
            ca[i][x - 1] = false;
            cb[j][x - 1] = false;
            cc[i / 3 * 3 + j / 3][x - 1] = false;
        }
        return false;
    }
}
